#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#include <conio.h>

// ================== 常量与类型定义区 ==================
#define MAP_ROWS 21
#define MAP_COLS 20
#define DOT '.'
#define WALL '#'
#define EMPTY ' '
#define PACMAN 'P'
#define GHOST 'G'
#define NAME_LEN 16
#define GHOST_COUNT 4

// --- ##### 排行榜结构体 ---
typedef struct {
    char name[NAME_LEN];
    int score;
} LeaderboardEntry;

// --- 二叉树结构体（通用） ---
typedef struct BinaryTreeNode {
    char name[16];
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BinaryTreeNode;

// ================== 数据结构层 ==================
// --- 队列（用于BFS） ---
typedef struct {
    int r, c;
} Point;

typedef struct {
    Point data[MAP_ROWS * MAP_COLS];
    int front, rear;
} Queue;

void queue_init(Queue* q) {
    // TODO: 待实现
}

int queue_empty(Queue* q) {
    // TODO: 待实现
    return 0;
}

void queue_push(Queue* q, int r, int c) {
    // TODO: 待实现
}

Point queue_pop(Queue* q) {
    // TODO: 待实现
    Point p = {0, 0};
    return p;
}

// --- 排序（通用） ---
void sort(LeaderboardEntry* arr, int n) {
    // TODO: 待实现
}

// --- 链表（通用，用于豆子） ---
typedef struct ListNode {
    int row, col;
    struct ListNode* next;
} ListNode;

typedef struct {
    ListNode* head;
    int count;
} LinkedList;

void LinkedList_init(LinkedList* list) {
    // TODO: 待实现
}

void LinkedList_insert(LinkedList* list, int row, int col) {
    // TODO: 待实现
}

int LinkedList_remove(LinkedList* list, int row, int col) {
    // TODO: 待实现
    return 0;
}

void LinkedList_free(LinkedList* list) {
    // TODO: 待实现
}

// --- 二叉树相关函数（通用） ---
BinaryTreeNode* BinaryTree_create(const char* name) {
    // TODO: 待实现
    return NULL;
}

void BinaryTree_insert_left(BinaryTreeNode* parent, BinaryTreeNode* child) {
    // TODO: 待实现
}

void BinaryTree_insert_right(BinaryTreeNode* parent, BinaryTreeNode* child) {
    // TODO: 待实现
}

void BinaryTree_free(BinaryTreeNode* root) {
    // TODO: 待实现
}

void BinaryTree_preorder(BinaryTreeNode* root) {
    // TODO: 待实现
}

int BinaryTree_depth(BinaryTreeNode* root) {
    // TODO: 待实现
    return 0;
}

int BinaryTree_count(BinaryTreeNode* root) {
    // TODO: 待实现
    return 0;
}

int BinaryTree_leaf_count(BinaryTreeNode* root) {
    // TODO: 待实现
    return 0;
}

// --- 二叉树构造（技能树示例） ---
BinaryTreeNode* BinaryTree_sample() {
    BinaryTreeNode* root = BinaryTree_create("RootSkill");
    BinaryTreeNode* left = BinaryTree_create("Attack");
    BinaryTreeNode* right = BinaryTree_create("Defense");
    BinaryTreeNode* leftleft = BinaryTree_create("Accelerate");
    BinaryTreeNode* leftright = BinaryTree_create("More One Life");
    BinaryTreeNode* rightleft = BinaryTree_create("Cross Wall");
    BinaryTreeNode* rightright = BinaryTree_create("Unbeatable");
    BinaryTree_insert_left(root, left);
    BinaryTree_insert_right(root, right);
    BinaryTree_insert_left(left, leftleft);
    BinaryTree_insert_right(left, leftright);
    BinaryTree_insert_left(right, rightleft);
    BinaryTree_insert_right(right, rightright);
    return root;
}

// --- 图结构体与BFS ---
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
} Graph;

void graph_init(Graph* g, char grid[MAP_ROWS][MAP_COLS]) {
    // TODO: 待实现
}

int graph_bfs(Graph* g, Point start, Point target, Point* path, int* path_len) {
    // TODO: 待实现
    return 0;
}

// ================== 逻辑层 ==================
typedef struct {
    char grid[MAP_ROWS][MAP_COLS];
    LinkedList dots;
} Map;

typedef struct {
    int row, col;
    int score;
    int lives;
} Pacman;

typedef struct {
    int row, col;
} Ghost;

static char map_data[MAP_ROWS][MAP_COLS+1] = {
    "####################",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#..................#",
    "#..##..####..##...#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "######.#.##.#.######",
    "#    #.#.##.#.#    #",
    "######.#.##.#.######",
    "#.................#",
    "######.#.##.#.######",
    "#    #.#.##.#.#    #",
    "######.#.##.#.######",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "#..##..####..##...#",
    "#..................#",
    "#....#.....#.....#.#",
    "#....#.....#.....#.#",
    "####################"
};

void map_init(Map* map) {
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map_data[i][j];
            map->grid[i][j] = c;
        }
    }
    LinkedList_init(&map->dots);
    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            if (map->grid[i][j] == DOT) {
                LinkedList_insert(&map->dots, i, j);
            }
        }
    }
}

int map_eat_dot(Map* map, int row, int col) {
    if (map->grid[row][col] != DOT) return 0;
    int removed = LinkedList_remove(&map->dots, row, col);
    if (removed) {
        map->grid[row][col] = EMPTY;
        return 1;
    }
    return 0;
}

void pacman_init(Pacman* p, int row, int col) {
    p->row = row; p->col = col; p->score = 0; p->lives = 3;
}

void ghost_init(Ghost* g, int row, int col) {
    g->row = row; g->col = col;
}

void pacman_draw(Pacman* p, Map* map) {
    map->grid[p->row][p->col] = PACMAN;
}

void ghost_draw(Ghost* g, Map* map) {
    map->grid[g->row][g->col] = GHOST;
}

void ghost_move(Map* map, Ghost* ghost, Pacman* pacman) {
    Graph g;
    graph_init(&g, map->grid);
    Point path[MAP_ROWS * MAP_COLS];
    int path_len;
    if (graph_bfs(&g, (Point){ghost->row, ghost->col}, (Point){pacman->row, pacman->col}, path, &path_len)) {
        if (path_len > 1) {
            ghost->row = path[1].r;
            ghost->col = path[1].c;
        }
    }
}

// ================== UI层 ==================
// Windows控制台设置函数
void setup_console() {
    // 获取控制台句柄
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    
    // 设置控制台字体
    CONSOLE_FONT_INFOEX fontInfo;
    fontInfo.cbSize = sizeof(fontInfo);
    GetCurrentConsoleFontEx(hConsole, FALSE, &fontInfo);
    wcscpy(fontInfo.FaceName, L"Consolas");
    fontInfo.dwFontSize.Y = 16;
    SetCurrentConsoleFontEx(hConsole, FALSE, &fontInfo);
}

// 使用ASCII字符定义墙体
const char* WALL_CHARS[] = {
    "+", // 十字
    "-", // 横线
    "|", // 竖线
    "+", // 左上
    "+", // 右上
    "+", // 左下
    "+", // 右下
    "+", // 左中
    "+", // 右中
    "+", // 上中
    "+"  // 下中
};

void map_draw(Map* map) {
    int ghost_color_idx = 0;
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    const WORD ghost_colors[] = {
        FOREGROUND_RED | FOREGROUND_INTENSITY,                    // 红色
        FOREGROUND_BLUE | FOREGROUND_INTENSITY,                   // 蓝色
        FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY, // 黄色
        FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY // 白色
    };

    for (int i = 0; i < MAP_ROWS; i++) {
        for (int j = 0; j < MAP_COLS; j++) {
            char c = map->grid[i][j];
            if (c == WALL) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
                int up = (i > 0 && map->grid[i-1][j] == WALL);
                int down = (i < MAP_ROWS-1 && map->grid[i+1][j] == WALL);
                int left = (j > 0 && map->grid[i][j-1] == WALL);
                int right = (j < MAP_COLS-1 && map->grid[i][j+1] == WALL);
                
                if (up || down) printf("|");
                else if (left || right) printf("-");
                else printf("+");
                
            } else if (c == DOT) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
                printf(".");
            } else if (c == PACMAN) {
                SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
                printf("C");  // 使用C代表Pacman
            } else if (c == GHOST) {
                SetConsoleTextAttribute(hConsole, ghost_colors[ghost_color_idx]);
                printf("G");  // 使用G代表Ghost
                ghost_color_idx = (ghost_color_idx + 1) % 4;
            } else {
                printf(" ");
            }
        }
        printf("\n");
        ghost_color_idx = 0;
    }
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
    printf("\nDots left: %d\n", map->dots.count);
}

void leaderboard_ui(LeaderboardEntry* lb, int n) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    sort(lb, n);
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("\n+======== Leaderboard ========+\n");
    
    for (int i = 0; i < n; i++) {
        printf("| ");
        if (i == 0) {
            SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
        } else {
            SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
        }
        printf("%-10s | %4d", lb[i].name, lb[i].score);
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf(" |\n");
    }
    
    printf("+===========================+\n");
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
}

void binarytree_print_with_color(BinaryTreeNode* node, int depth, int isLast, int isRoot) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    for (int i = 0; i < depth; i++) {
        printf("| ");  // 改为竖线表示层级
    }
    if (depth > 0) {
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf("|-");  // 统一使用|-连接
    }
    if (isRoot) {
        SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
        printf("%s\n", node->name);
    } else {
        SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
        printf("%s\n", node->name);
    }
    if (node->left && node->right) {
        binarytree_print_with_color(node->left, depth+1, 0, 0);
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    } else if (node->left) {
        binarytree_print_with_color(node->left, depth+1, 1, 0);
    } else if (node->right) {
        binarytree_print_with_color(node->right, depth+1, 1, 0);
    }
}

void binarytree_ui(BinaryTreeNode* root) {
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("\n+====== Skill Tree ======+\n");
    if (root)
        binarytree_print_with_color(root, 0, 1, 1);
    SetConsoleTextAttribute(hConsole, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("+=======================+\n");
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Total Skills: ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_count(root));
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Skills Level(Tree Depth): ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_depth(root));
    
    SetConsoleTextAttribute(hConsole, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
    printf("Real Powerful Skills(Leaf count): ");
    SetConsoleTextAttribute(hConsole, FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    printf("%d\n", BinaryTree_leaf_count(root));
}

// Windows版本的键盘输入检测
int kbhit() {
    return _kbhit();
}

// ================== 主函数 ==================
int main() {
    // 设置控制台
    setup_console();
    
    Map map;
    Pacman pacman;
    Ghost ghosts[GHOST_COUNT];
    LeaderboardEntry lb[5] = { {"Alice", 120}, {"Bob", 200}, {"Carol", 150}, {"You", 0}, {"Test", 0} };
    char playerName[NAME_LEN] = "You";
    
    srand(time(NULL));
    map_init(&map);
    pacman_init(&pacman, 10, 10);
    ghost_init(&ghosts[0], 1, 2);
    ghost_init(&ghosts[1], 1, 17);
    ghost_init(&ghosts[2], 19, 2);
    ghost_init(&ghosts[3], 19, 17);
    
    int frame = 0;
    int running = 1;
    
    while (running) {
        system("cls");  // Windows清屏命令
        
        for (int i = 0; i < MAP_ROWS; i++)
            for (int j = 0; j < MAP_COLS; j++)
                if (map.grid[i][j] == PACMAN || map.grid[i][j] == GHOST)
                    map.grid[i][j] = EMPTY;
        
        pacman_draw(&pacman, &map);
        for (int i = 0; i < GHOST_COUNT; i++)
            ghost_draw(&ghosts[i], &map);
        
        map_draw(&map);
        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
        printf("\nName: %s  Score: %d  Lives: %d\n", playerName, pacman.score, pacman.lives);
        
        if (kbhit()) {
            char key = _getch();
            int dr = 0, dc = 0;
            if (key == 'w' || key == 'W') dr = -1;
            if (key == 's' || key == 'S') dr = 1;
            if (key == 'a' || key == 'A') dc = -1;
            if (key == 'd' || key == 'D') dc = 1;
            int nr = pacman.row + dr, nc = pacman.col + dc;
            if (nr >= 0 && nr < MAP_ROWS && nc >= 0 && nc < MAP_COLS && map.grid[nr][nc] != WALL) {
                pacman.row = nr; pacman.col = nc;
                if (map_eat_dot(&map, nr, nc)) pacman.score += 10;
            }
        }
        
        if (frame % 2 == 0) {
            for (int i = 0; i < GHOST_COUNT; i++) {
                ghost_move(&map, &ghosts[i], &pacman);
                if (ghosts[i].row == pacman.row && ghosts[i].col == pacman.col) {
                    pacman.lives--;
                    if (pacman.lives <= 0) running = 0;
                }
            }
        }
        
        if (map.dots.count == 0) running = 0;
        Sleep(120);  // Windows睡眠函数，单位为毫秒
        frame++;
    }
    
    printf("\nGame Over!\n");
    lb[3].score = pacman.score;
    leaderboard_ui(lb, 5);
    BinaryTreeNode* skillroot = BinaryTree_sample();
    binarytree_ui(skillroot);
    BinaryTree_free(skillroot);
    LinkedList_free(&map.dots);
    
    // 恢复默认颜色
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
    return 0;
} 
